package main

import (
	"fmt"
)

/**
60. 第k个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"
*/

/**
显然不能暴力把 所有的数都求出来再排序，内存分分钟爆掉
我们分析每一个数生成的策略，从小开始生成，比如 n=4,数组d表示生成的一个数字
给d的每一位选择分支时，实际上就是创建了一个分支，如最开始 d[3] 可选的是1,2,3,4,当 d[3]=1时，d[2]有 2,3,4选择，此时，数字的生成就变成了一个树
          1
         /|\
       /  | \
      2  3  4
     /\	....
    3  4	....
    |  |	....
    4  3	....
    |  |	....
1234   1243	....
可以看出来，每个分支，所能产生的叶子节点数是确定的，我们生成数字的规则也是从小都大的，那么就可以判断出 第 K 为再那个分支上，该叶子节点的值就是答案
如 n=4,k=9, treeNum 为遍历的节点的叶子节点数
d[3]=1时，treeNum (3!=6)<9,所有答案不会落在以 1 开头的数字，为了方便计算，没经过一个节点，如果答案不落在上面，就减去改节点的叶子节点数
k=9-6=3
d[3] = 2, treeNum=6, 6 > 3 ，所以答案应该落在2开头的数字
剩下 可选的是 1,3,4,
d[2] = 1 时，treeNum = 2 , k>treeNum,k=k-treeNum =1
d[2] =3 时，treeNum = 2 , 1<2 ,选择该分支，剩下可选数字 1 ，4
d[1] =1 时，treeNum= 1,1 ==1 ,选择 剩下 4
d[0]=4
答案就是 2 3 1 4

使用一个数组来保存每个数字是否已经被使用，每次遍历，改变K的值，当 k=0 时 ，答案出现

*/

func main() {
	fmt.Println(getPermutation(4, 9))
}
func getPermutation(n int, k int) string {
	ans := make([]byte, n)
	fact := make([]int, n+1)
	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = i * fact[i-1]
	}
	use := make([]bool, n+1)
	// 剩下选择的个数
	index := n
	for index > 0 {
		// 从小往大遍历
		for i := 1; i <= n; i++ {
			// 当前值未使用
			if !use[i] {
				if k > fact[index-1] {
					k = k - fact[index-1]
					continue
				}
				ans[n-index] = '0' + byte(i)
				use[i] = true
				index--
				break
			}
		}
	}
	return string(ans)
}
